//给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果 target 存在返
//回下标，否则返回 -1。 
//
// 你必须编写一个具有 O(log n) 时间复杂度的算法。 
//
// 示例 1: 
//
// 
//输入: nums = [-1,0,3,5,9,12], target = 9
//输出: 4
//解释: 9 出现在 nums 中并且下标为 4
// 
//
// 示例 2: 
//
// 
//输入: nums = [-1,0,3,5,9,12], target = 2
//输出: -1
//解释: 2 不存在 nums 中因此返回 -1
// 
//
// 
//
// 提示： 
//
// 
// 你可以假设 nums 中的所有元素是不重复的。 
// n 将在 [1, 10000]之间。 
// nums 的每个元素都将在 [-9999, 9999]之间。 
// 
//
// Related Topics 数组 二分查找 👍 1777 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    //尼玛的，卧槽，快四十的人了，还刷算法题。
    public int search(int[] nums, int target) {
        int i = 0;
        int j = nums.length - 1;
        while(i <= j){
////            int mid =(j-i)/2 +i;
//            int mid =(j+i)/2;
//            int num = nums[mid];
//            if(num == target)
//                return mid;
//            else if(target < num){//目标在左边
//                j = mid -1;
//            }else if(target > num){//目标在右边
//                i = mid + 1 ;
//            }
            int mid = (i + j) >>> 1;
            if (target < nums[ mid]){
                j = mid - 1;
            }else if(target > nums[mid]){
                i = mid + 1;
            }else {
                return mid;
            }
        }
        return -1;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
